#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#define limit 1000 //阈值

typedef struct point
{
	double x, y;
	int tag;
};
void get_max(point p_set[], int left, int right, double &max_des, int &max_point)
{
	point p1, p2;
	p1 = p_set[left];
	p2 = p_set[right];
	// 点到直线距离
	double normalLen = (sqrt((p1.y - p2.y) * (p1.y - p2.y) + (p1.x - p2.x) * (p1.x - p2.x)));
	max_des = -1;
	double des;
	for (int i = left; i < right; i++)
	{
		point p3 = p_set[i];
		des = fabs((p3.x - p1.x) * (p2.y - p1.y) - (p3.y - p1.y) * (p2.x - p1.x)) / normalLen;
		if (des > max_des)
		{
			max_des = des;
			max_point = i;
		}
	}
}
void d_fun(point p_set[], int left, int right)
{
	//1.递归结束
	if (right - left < 2)
		return;
	//2.找出max_des getmax()
	if (p_set[left].x == p_set[right].x && p_set[left].y == p_set[right].y)
	{
		int half = (left + right) / 2;
		d_fun(p_set, left, half);
		d_fun(p_set, half, right);
	}
	double max_des;
	int max_point;
	get_max(p_set, left, right, max_des, max_point);
	//3.if (max_des<limit) 点全部舍弃
	if (max_des < limit)
	{
		for (int i = left + 1; i < right; i++)
		{
			p_set[i].tag = 0;
		}
	}
	//4.else 对左右点集进行递归
	else
	{
		d_fun(p_set, left, max_point);
		d_fun(p_set, max_point, right);
	}
}
void douglas(point p_set[], int &n)
{
	//1 douglas算法
	d_fun(p_set, 0, n - 1);
}

FILE *fp = fopen("E:\\Desktop\\data_struct\\11GIS\\douglas\\china_1.txt", "r");
FILE *c_fp = fopen("E:\\Desktop\\data_struct\\11GIS\\douglas\\compress_china_1500.txt", "w");
void *read_line()
{
	while (1)
	{
		char index_[5];
		int index;
		if (fscanf(fp, "%s", index_) == EOF)
			break;

		if ((index_[0] == 'E') && (index_[1] == 'N') && (index_[2] == 'D'))
			break;
		index = atoi(index_);
		point *p_set = (point *)malloc(sizeof(point) * 1000);

		double x_f, y_f;
		int count = 0;
		while (fscanf(fp, "%lf,%lf", &x_f, &y_f) == 2)
		{
			p_set[count].x = x_f;
			p_set[count].y = y_f;
			p_set[count].tag = 1;
			count++;
		}
		char test[5];
		fscanf(fp, "%4s", test);
		douglas(p_set, count);
		//write
		fprintf(c_fp, "%d\n", index);
		for (int i = 0; i < count; i++)
		{
			if (p_set[i].tag == 1)
			{
				int m = fprintf(c_fp, "%.8lf,%.8lf\n", p_set[i].x, p_set[i].y);
				m = m;
			}
		}
		fprintf(c_fp, "END\n");
	}
	fprintf(c_fp, "END\n");
}
int main()
{
	/*******************code*******************/
	read_line();

	/******************************************/
	fflush(stdin);

	printf("\n\n****************************\n");
	printf("Press Enter key to continue\n");
	getchar();
	return 0;
	/******************************************/
}
